class Solution {
public:
    int n;
    long long cnt;
    const long long Mod = 1e9 + 7;
    int st[15] = { 0 };
    int path[15] = { 0 }, pos = 0;
    bool check()
    {
        for (int i = 0; i < n - 1; i++) {
            if (path[i] % path[i + 1] != 0 && path[i + 1] % path[i] != 0)
                return false;
        }
        return true;
    }
    void dfs(vector<int>& nums)
    {
        if (pos == n)
        {
            if (check()) cnt++;
            cnt %= Mod;
        }
        for (int i = 0; i < n; i++)
        {
            if (!st[i])
            {
                st[i] = true;
                path[pos] = nums[i];
                pos++;
                dfs(nums);
                st[i] = false;
                pos--;
                path[pos] = 0;
            }
        }
    }
    int specialPerm(vector<int>& nums) {
        n = nums.size();

        dfs(nums);
        return cnt;
    }
};